package com.ln.prac.base.m202206.d23;


import com.ln.prac.base.core.SortHelper;

import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import java.util.Random;
import java.util.stream.Collectors;

/**
 * <pre>
 *  TODO
 * </pre>
 *
 * @Author zhangj
 * @Date 2022/6/23 11:56
 */
public class SortSort {

    public static List<Integer> f1(List<Integer> list) {
        if(list.size() <= 0) {
            return list;
        }
        Integer num = list.get(0);
        List<Integer> left = list.stream().filter(x-> x < num).collect(Collectors.toList());
        List<Integer> middle = list.stream().filter(x-> Objects.equals(x, num)).collect(Collectors.toList());
        List<Integer> right = list.stream().filter(x-> x > num).collect(Collectors.toList());

        left = f1(left);
        right = f1(right);

        left.addAll(middle);
        left.addAll(right);

        return left;
    }

    public static void f2(Integer[] A) {
        f2(A, 0, A.length);
    }

    private static void f2(Integer[] A, int l, int r) {
        if(r - l <= 1) {
            return;
        }
        // 对数据进行分组为左中右，返回结果下标
        int mid = partition(A, l, r);
        // 递归
        f2(A, l, mid);
        f2(A, mid, r);
        // 合并
        merge(A, l, mid, r);
    }

    private static void merge(Integer[] A, int l, int mid, int r) {
        Integer[] B = Arrays.copyOfRange(A, l, mid + 1);
        Integer[] C = Arrays.copyOfRange(A, mid, r + 1);

        B[B.length - 1] = C[C.length - 1] = Integer.MAX_VALUE;

        int i = 0, j = 0;
        for (int k = l; l < r; l++) {
            if(B[i] < C[j]) {
                A[k] = B[i++];
            }
            else {
                A[k] = C[j++];
            }
        }
    }

    private static int partition(Integer[] A, int l, int r) {
        int num = A[l];
        int i = l + 1, j = r;

        while (i != j) {
            if(A[i] < num) {
                ++i;
            } else {
                SortHelper.swap(A, i, --j);
            }
        }

        SortHelper.swap(A, i - 1, l);
        return i - 1;
    }




    public static void main(String[] args) {
        Integer[] A = new Integer[20];
        Random random = new Random();
        for (int i = 0; i < 20; i++) {
            A[i] = random.nextInt(100);
        }
//        System.out.println(f1(Arrays.asList(A)));

        f2(A);
        System.out.println(Arrays.asList(A));

    }

}
